public class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0; // 如果数组为空或只有一个元素，最大间距为0
        }

        int m = Integer.MAX_VALUE;
        int M = Integer.MIN_VALUE;
        for (int x : nums) {
            m = Math.min(m, x);
            M = Math.max(M, x);
        }
        if (M - m <= 1) {
            return M - m;
        }

        int n = nums.length;
        int d = (M - m + n - 2) / (n - 1); // 答案至少是 d
        int[][] buckets = new int[(M - m) / d + 1][2];
        for (int[] b : buckets) {
            b[0] = Integer.MAX_VALUE;
            b[1] = Integer.MIN_VALUE;
        }
        for (int x : nums) {
            int[] b = buckets[(x - m) / d];
            b[0] = Math.min(b[0], x); // 维护桶内元素的最小值和最大值
            b[1] = Math.max(b[1], x);
        }

        int ans = 0;
        int preMax = Integer.MAX_VALUE;
        for (int[] b : buckets) {
            if (b[0] != Integer.MAX_VALUE) { // 非空桶
                // 桶内最小值，减去上一个非空桶的最大值
                if (preMax != Integer.MAX_VALUE) {
                    ans = Math.max(ans, b[0] - preMax);
                }
                preMax = b[1];
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {3, 6, 9, 1};
        System.out.println("最大间距: " + solution.maximumGap(nums1)); // 输出 9 - 1 = 8
    }
}